package _18_剑指OfferII;

import java.util.ArrayList;
import java.util.List;

public class _087_剑指OfferII复原IP {

    public static void main(String[] args) {

        _087_剑指OfferII复原IP v = new _087_剑指OfferII复原IP();

        String str = "10203040";

        List<String> strings = v.restoreIpAddresses(str);

        System.out.println(strings);

    }

    private List<String> results = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        int len = s.length();
        dfs(s, 0, 0, len, new StringBuilder());
        return results;
    }

    private void dfs(String s, int start, int count, int len, StringBuilder stringBuilder) {
        int originLen = stringBuilder.length();
        if (count == 4) {
            if (start == len)
                results.add(stringBuilder.delete(originLen - 1, originLen).toString());
            return;
        }

        for (int i = start; i < len; i++) {
            String subStr = s.substring(start, i + 1);
            if (!isLegalIp(subStr)) break;
            stringBuilder.append(subStr).append(".");
            dfs(s, i + 1, count + 1, len, stringBuilder);
            stringBuilder.delete(originLen, stringBuilder.length());
        }

    }

    private boolean isLegalIp(String s) {
        if (s.length() > 1 && s.charAt(0) == '0') {
            // 包含前导0
            return false;
        }
        int len = s.length();
        int total = 0;
        for (int i = 0; i < len; i++) {
            total = total * 10 + (s.charAt(i) - '0');
        }
        return total <= 255;
    }

}
